A semiconductor memory device using a semiconductor memory chip has been widely used in recent years due to increased capacity of a NAND-type flash memory (referred to as a NAND memory), which is one type of the semiconductor memory chip. In writing to a NAND memory, the NAND memory needs to be erased before the writing. A NAND memory is erased in blocks, such as in units of 512 KB. This is significantly large relative to 4 KB, which is a data size used relatively often in writing according to a request from a host, which is a host device of a semiconductor memory device. The size of 4 KB corresponds to the size of a page, for example, which is a smaller unit than a block. If erasure is performed each time before writing of data, erasure in units of a 512-KB block is performed for writing in units of a 4-KB page.
Meanwhile, there is an upper limit set for the number of erasures of the NAND memory as a characteristic of a semiconductor memory chip, and it is undesirable to exceed the upper limit in terms of reliability. In the related art, a log-structure that has been long used in file systems and databases, for example, is used to control the number of erasures. In this technique, data is written in an erased block in units of a 4-KB page sequentially in the order of pages regardless of a logical block address (LBA) specified by a host, the association of a physical address (PA) indicating a physical storage location where data is written and the logical block address is stored, and data is read using the association of addresses. This system is called a log-structured method.
A plurality of requests for writing different data to the same logical block address may be made. These different data are basically written in different pages. A page in which old data (referred to as invalid data) is written becomes invalid and a page in which new data (referred to as valid data) is written becomes valid. When the amount of invalid data increases, the capacity of a NAND memory at which writing can be realized (referred to as realizable capacity) gradually decreases. When a new erased block in which data can be written, namely a block (referred to as a free block) in which data is not yet written after erasure thereof, cannot be reserved any longer, writing becomes impossible. To avoid this, the semiconductor memory device collects valid data in blocks containing invalid data, newly rewrites the collected valid data in free blocks to move the valid data thereto, erases, as blocks containing only invalid data, the blocks from which the valid data are moved, and performs garbage collection to newly generate free blocks. The garbage collection performed in a NAND memory using the log-structured method is particularly referred to as compaction. In the semiconductor memory device, blocks that were unwritable become writable again by performing the compaction, allowing free blocks to be reserved.
In the related art, the compaction is performed when the free blocks are exhausted or immediately before they are exhausted. However, when the compaction is performed, the bandwidth of the NAND memory is squeezed due to reading and writing of valid data, which may lead to significant decrease in response speed to data write requests from the host.